//
// Created by LiuYou on 2021/11/29.
//

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>


/*
 * 内部的循环每次是把最大的值交换到了最后的位置。
 *
 * 这个是正确的。
 */
static void bubbleSort(std::vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }

    // 0 ~ i
    // 第一个循环指的是: 我要在 0 ~ i 的位置上, 相邻两个数交换。
    // 然后循环结束后, 我继续在 0 ~ i-1 的位置上, 相邻两个数交换。
    // ...
    for (int i = arr.size() - 1; i > 0; --i) {
        // 第二个for循环指的是: j 从 0 出发, j < i。
        // 每次对比后一个数是否比前一个数大。
        // 如果有那就交换。
        for (int j = 0; j < i; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap( arr[j], arr[j + 1] );
            }
        }
    }
}


int main(int argc, char** argv) {
    {
        std::vector<int> arr{3, 2, 5, 4, 1};
        bubbleSort( arr );
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, " " ));
        std::cout << std::endl;
    }

    {
        std::vector<int> arr{33, 51, 656, 626, 721, 36, 721, 4, 7, 271, 1, 76, 4};
        std::vector<int> arr2( arr );

        {
            bubbleSort( arr );
            std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, " " ));
            std::cout << std::endl;
        }

        {
            std::copy( arr2.begin(), arr2.end(), std::ostream_iterator<int>( std::cout, " " ));
            std::cout << std::endl;
            std::sort( arr2.begin(), arr2.end());
            std::copy( arr2.begin(), arr2.end(), std::ostream_iterator<int>( std::cout, " " ));
            std::cout << std::endl;
        }
    }

    return 0;
}

